#include "sky2.h"

using namespace std;

Skyline2::Skyline2(int w, int h)
		: width(w), height(h)
{
}

void Skyline2::save(vector<Skyline2::rect> &rlist){

}

std::vector<Skyline2::rect>  Skyline2::solve(std::vector<Skyline2::rect> rectangles,int *hf)
{
	vector<int>Skyline2;

	sort(rectangles.begin(),rectangles.end(),comparew);
	for(int i=0;i<width;i++){
		Skyline2.push_back(0);
	}
//	for(int i=0;i<rectangles.size();i++){
//		cout<<rectangles[i].w<<" "<<rectangles[i].h<<endl;
//	}
	int h1,h2,h3;
	vector<struct rect>rlist1;
	packleftmost(rectangles,Skyline2,&h1,rlist1);
	//vector<struct rect>rlist2=packtotall(rectangles,Skyline2,&h2);
	//vector<struct rect>rlist3=packtoshort(rectangles,Skyline2,&h3);
   //cout<<h1<<" "<<h2<<" "<<h3<<endl;
   *hf=h1;
   save(rlist1);

	/*if(h1<h2){
		if(h1<h3)
		{
			hf = h1;
			save(rlist1);
		}
		else
		{	hf = h3;
			save(rlist3);
		}
	}else{
		if(h2<h3)
		{
			hf = h2;
			save(rlist2);
		}
		else
		{
			hf = h3;
			save(rlist3);
		}
	}*/

	return rlist1;

//	sort(rlist.begin(),rlist.end(),comparew);

}



bool comparew(const Skyline2::rect& x, const Skyline2::rect& y){
	if(x.w==y.w)return x.h<y.h;
	return x.w<y.w;
}

int Skyline2::getlowest(vector<int>& sky){
	int j=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]<sky[j])j=i;
	}
	return j;
}

vector<Skyline2::rect> Skyline2::packleftmost(vector<Skyline2::rect>rls,vector<int>sky,int *hh,vector<Skyline2::rect>&ret){
	ret.clear();
	while(rls.size()){
/*		cout<<rls.size()<<endl;
		for(int i=0;i<sky.size();i++){
			cout<<sky[i]<<" ";
		}
		cout<<endl;*/
		int j=getlowest(sky);
		int k=j;
		while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
		int gap=k-j;
		int found=0;
		int best=rls.size()-1;
		int mingap=gap;
		if(rls[best].h<gap){
			mingap=gap-rls[best].h;
		}
		if(rls[best].w<gap && gap-rls[best].w<mingap){
			mingap=gap-rls[best].w;
		}
		for(int i=rls.size()-1;i>=0;i--){
			if(rls[i].w==gap){
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h==gap){

				swap(rls[i].h,rls[i].w);
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h<gap){
				if(gap-rls[i].h<mingap){
					best=i;
					mingap=gap-rls[i].h;
				}
			}
			if(rls[i].w<gap){
				if(gap-rls[i].w<mingap){
					best=i;
					mingap=gap-rls[i].w;
				}
			}

		}
                if(!found  && rls[best].w<=gap && mingap==gap-rls[best].w){
			int i=best;
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			ret[m].x=j;
			ret[m].y=sky[j];
			for(int i=j;i<j+ret[m].w;i++)
				sky[i]+=ret[m].h;
			found=1;
		}
		else if(!found && rls[best].h<=gap && mingap==gap-rls[best].h){
			int i=best;
			swap(rls[i].h,rls[i].w);
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			ret[m].x=j;
			ret[m].y=sky[j];
			for(int i=j;i<j+ret[m].w;i++)
				sky[i]+=ret[m].h;
			found=1;
		}
		if(found==0){
//			cout<<j<<" "<<sky[j]<<endl;
			int h1=0,h2=0;
			if(j>0)
				h1=sky[j-1];
			if(k<sky.size())
				h2=sky[k];
			for(int i=j;i<k;i++)
				sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
		}

	}
	//return ret;
	int op=0;
	vector<Skyline2::rect> retnew=ret;
	vector<int> skynew=sky;
	while(op==0){
		int maxh=0,max=0;

		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[maxh])maxh=i;
		}
		max=sky[maxh];

		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].w>=ret[i].h){
					op=1;
					break;
				}
			}
		}
		if(op==1)break;
		int maxr=ret.size()-1;
		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				maxr=i;
				//cout<<max<<" "<<maxh<<" "<<maxr<< " "<<ret[maxr].y<<endl;
				//printsky(sky);
				for(int j=ret[maxr].x;j<ret[maxr].x+ret[maxr].w;j++){
					sky[j]-=(ret[maxr].h);
				}
				//printsky(sky);
				swap(ret[maxr].w,ret[maxr].h);
				rls.push_back(ret[maxr]);
				ret.erase(ret.begin()+maxr);
				break;
			}
		}
		while(rls.size()){
			//cerr<<sky[0]<<endl;
			//printsky(sky);
			int j=getlowest(sky);
			int k=j;
			while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
			int gap=k-j;
			int found=0;
			int best=rls.size()-1;

			for(int i=rls.size()-1;i>=0;i--){
				if(rls[i].w<=gap){
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					ret[m].x=j;
					ret[m].y=sky[j];
					//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
					for(int i=j;i<j+ret[m].w;i++)
						sky[i]+=ret[m].h;
					found=1;
					break;
				}
			}
			if(k-j>=width)
				break;

			if(found==0){
				int h1=0,h2=0;
				if(j>0)
					h1=sky[j-1];
				if(k<sky.size())
					h2=sky[k];
				for(int i=j;i<k;i++){
					if(h1==h2 && h1==0){
						//cerr<<j<<" "<<k<<" "<<width<<endl;
						break;
					}
					sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
				}
			}

		}



		int newmaxh=0;
		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[newmaxh])newmaxh=i;
		}
		//cerr<< sky[newmaxh]<< " "<<max<<endl;
		if(sky[newmaxh]<max){
			op=0;
			retnew=ret;
			skynew=sky;
		}
		else{
			op=1;
			ret=retnew;
			sky=skynew;
		}


	}
	int newmaxh=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]>sky[newmaxh])newmaxh=i;
	}
	*hh=sky[newmaxh];

	//printsky(sky);
	return ret;
}
vector<Skyline2::rect> Skyline2::packtotall(vector<Skyline2::rect>rls,vector<int>sky,int * hh){
	vector<Skyline2::rect> ret;
	while(rls.size()){
/*		cout<<rls.size()<<endl;
		for(int i=0;i<sky.size();i++){
			cout<<sky[i]<<" ";
		}
		cout<<endl;*/
		int j=getlowest(sky);
		int k=j;
		while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
		int gap=k-j;
		int found=0;
		int best=rls.size()-1;
		int mingap=gap;
		if(rls[best].h<gap){
			mingap=gap-rls[best].h;
		}
		if(rls[best].w<gap && gap-rls[best].w<mingap){
			mingap=gap-rls[best].w;
		}

		for(int i=rls.size()-1;i>=0;i--){
			if(rls[i].w==gap){
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h==gap){
				swap(rls[i].h,rls[i].w);
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h<gap){
				if(gap-rls[i].h<mingap){
					best=i;
					mingap=gap-rls[i].h;
				}
			}
			if(rls[i].w<gap){
				if(gap-rls[i].w<mingap){
					best=i;
					mingap=gap-rls[i].w;
				}
				break;
			}

		}
                if(!found  && rls[best].w<=gap && mingap==gap-rls[best].w){
			int i=best;
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else if(k==sky.size()){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
			}

			found=1;
		}
		else if(!found && rls[best].h<=gap && mingap==gap-rls[best].h){
			int i=best;
			swap(rls[i].h,rls[i].w);
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
			}
			else if(k==sky.size()){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			found=1;
		}
		if(found==0){
			int h1=0,h2=0;
			if(j>0)
				h1=sky[j-1];
			if(k<sky.size())
				h2=sky[k];
			for(int i=j;i<k;i++)
				sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
		}

	}
	//return ret;
	int op=0;
	vector<Skyline2::rect> retnew=ret;
	vector<int> skynew=sky;
	while(op==0){
		int maxh=0,max=0;

		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[maxh])maxh=i;
		}
		max=sky[maxh];

		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].w>=ret[i].h){
					op=1;
					break;
				}
			}
		}
		if(op==1)break;
		int maxr=ret.size()-1;
		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				maxr=i;
				//cout<<max<<" "<<maxh<<" "<<maxr<< " "<<ret[maxr].y<<endl;
				//printsky(sky);
				for(int j=ret[maxr].x;j<ret[maxr].x+ret[maxr].w;j++){
					sky[j]-=(ret[maxr].h);
				}
				//printsky(sky);
				swap(ret[maxr].w,ret[maxr].h);
				rls.push_back(ret[maxr]);
				ret.erase(ret.begin()+maxr);
				break;
			}
		}
		while(rls.size()){
			//cerr<<sky[0]<<endl;
			//printsky(sky);
			int j=getlowest(sky);
			int k=j;
			while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
			int gap=k-j;
			int found=0;
			int best=rls.size()-1;

			for(int i=rls.size()-1;i>=0;i--){
				if(rls[i].w==gap){
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					ret[m].x=j;
					ret[m].y=sky[j];
					//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
					for(int i=j;i<j+ret[m].w;i++)
						sky[i]+=ret[m].h;
					found=1;
					break;
				}
				if(rls[i].w<gap){
					int mingap=gap-rls[i].w;
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					if(j==0){
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;

					}
					else if(k==sky.size()){
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;
					}
					else if(sky[j-1]<sky[k]){
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;
					}
					else{
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;
					}
					found=1;
					break;
				}
			}
			if(k-j>=width)
				break;

			if(found==0){
				int h1=0,h2=0;
				if(j>0)
					h1=sky[j-1];
				if(k<sky.size())
					h2=sky[k];
				for(int i=j;i<k;i++){
					if(h1==h2 && h1==0){
						//cerr<<j<<" "<<k<<" "<<width<<endl;
						break;
					}
					sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
				}
			}

		}



		int newmaxh=0;
		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[newmaxh])newmaxh=i;
		}
		//cerr<< sky[newmaxh]<< " "<<max<<endl;
		if(sky[newmaxh]<max){
			op=0;
			retnew=ret;
			skynew=sky;
		}
		else{
			op=1;
			ret=retnew;
			sky=skynew;
		}


	}
	int newmaxh=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]>sky[newmaxh])newmaxh=i;
	}
	*hh=sky[newmaxh];
	//printsky(sky);
	return ret;
}
vector<Skyline2::rect> Skyline2::packtoshort(vector<Skyline2::rect>rls,vector<int>sky,int *hh){
	vector<Skyline2::rect> ret;
	while(rls.size()){
/*		cout<<rls.size()<<endl;
		for(int i=0;i<sky.size();i++){
			cout<<sky[i]<<" ";
		}
		cout<<endl;*/
		int j=getlowest(sky);
		int k=j;
		while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
		int gap=k-j;
		int found=0;
		int best=rls.size()-1;
		int mingap=gap;
		if(rls[best].h<gap){
			mingap=gap-rls[best].h;
		}
		if(rls[best].w<gap && gap-rls[best].w<mingap){
			mingap=gap-rls[best].w;
		}

		for(int i=rls.size()-1;i>=0;i--){
			if(rls[i].w==gap){
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h==gap){

				swap(rls[i].h,rls[i].w);
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h<gap){
				if(gap-rls[i].h<mingap){
					best=i;
					mingap=gap-rls[i].h;
				}
			}
			if(rls[i].w<gap){
				if(gap-rls[i].w<mingap){
					best=i;
					mingap=gap-rls[i].w;
				}
				break;
			}

		}
                if(!found  && rls[best].w<=gap && mingap==gap-rls[best].w){
			int i=best;
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else if(k==sky.size()){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}

			found=1;
		}
		else if(!found && rls[best].h<=gap && mingap==gap-rls[best].h){
			int i=best;
			swap(rls[i].h,rls[i].w);
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;
			}
			else if(k==sky.size()){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			found=1;
		}
		if(found==0){
			int h1=0,h2=0;
			if(j>0)
				h1=sky[j-1];
			if(k<sky.size())
				h2=sky[k];
			for(int i=j;i<k;i++)
				sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
		}

	}
	//return ret;
	int op=0;
	vector<Skyline2::rect> retnew=ret;
	vector<int> skynew=sky;
	while(op==0){
		int maxh=0,max=0;

		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[maxh])maxh=i;
		}
		max=sky[maxh];

		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].w>=ret[i].h){
					op=1;
					break;
				}
			}
		}
		if(op==1)break;
		int maxr=ret.size()-1;
		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				maxr=i;
				//cout<<max<<" "<<maxh<<" "<<maxr<< " "<<ret[maxr].y<<endl;
				//printsky(sky);
				for(int j=ret[maxr].x;j<ret[maxr].x+ret[maxr].w;j++){
					sky[j]-=(ret[maxr].h);
				}
				//printsky(sky);
				swap(ret[maxr].w,ret[maxr].h);
				rls.push_back(ret[maxr]);
				ret.erase(ret.begin()+maxr);
				break;
			}
		}
		while(rls.size()){
			//cerr<<sky[0]<<endl;
			//printsky(sky);
			int j=getlowest(sky);
			int k=j;
			while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
			int gap=k-j;
			int found=0;
			int best=rls.size()-1;

			for(int i=rls.size()-1;i>=0;i--){
				if(rls[i].w==gap){
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					ret[m].x=j;
					ret[m].y=sky[j];
					//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
					for(int i=j;i<j+ret[m].w;i++)
						sky[i]+=ret[m].h;
					found=1;
					break;
				}
				if(rls[i].w<gap){
					int mingap=gap-rls[i].w;
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					if(j==0){
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;

					}
					else if(k==sky.size()){
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;
					}
					else if(sky[j-1]<sky[k]){
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;
					}
					else{
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;
					}
					found=1;
					break;
				}
			}
			if(k-j>=width)
				break;

			if(found==0){
				int h1=0,h2=0;
				if(j>0)
					h1=sky[j-1];
				if(k<sky.size())
					h2=sky[k];
				for(int i=j;i<k;i++){
					if(h1==h2 && h1==0){
						//cerr<<j<<" "<<k<<" "<<width<<endl;
						break;
					}
					sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
				}
			}

		}



		int newmaxh=0;
		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[newmaxh])newmaxh=i;
		}
		//cerr<< sky[newmaxh]<< " "<<max<<endl;
		if(sky[newmaxh]<max){
			op=0;
			retnew=ret;
			skynew=sky;
		}
		else{
			op=1;
			ret=retnew;
			sky=skynew;
		}


	}
	int newmaxh=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]>sky[newmaxh])newmaxh=i;
	}
	*hh=sky[newmaxh];
	//printsky(sky);
	return ret;
}


